// https://leetcode.cn/problems/minimum-number-of-frogs-croaking/description/

// 算法思路总结：
// 1. 模拟青蛙鸣叫顺序，统计同时鸣叫的青蛙数量
// 2. 使用哈希数组跟踪每个字母的出现次数
// 3. 按"croak"顺序处理字符，确保合法性
// 4. 检查最终状态是否所有青蛙完成鸣叫
// 5. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>

class Solution 
{
public:
    int minNumberOfFrogs(string croakOfFrogs) 
    {
        string croak = "croak";
        int n = croak.size();
        unordered_map<char, int> index;

        for (int i = 0 ; i < n ; i++)
        {
            index[croak[i]] = i;
        }

        vector<int> hash(n, 0);
        for (int i = 0 ; i < croakOfFrogs.size() ; i++)
        {
            char ch = croakOfFrogs[i];
            if (ch == 'c')
            {
                if (hash[n - 1] > 0)
                {
                    hash[n - 1]--;
                    hash[0]++;
                }
                else
                {
                    hash[0]++;
                }
            }
            else
            {
                if (hash[index[ch] - 1] > 0)
                {
                    hash[index[ch] - 1]--;
                    hash[index[ch]]++;
                }
                else
                {
                    return -1;
                }
            }
        }

        for (int i = 0 ; i < n - 1; i++)
        {
            if (hash[i] != 0)
            {
                return -1;
            }
        }

        return hash[n - 1];
    }
};

int main()
{
    string croakOfFrogs1 = "croakcroak", croakOfFrogs2 = "crcoakroak";
    Solution sol;
    
    cout << sol.minNumberOfFrogs(croakOfFrogs1) << endl;
    cout << sol.minNumberOfFrogs(croakOfFrogs2) << endl;

    return 0;
}